interface ListNode {
	val: number;
	next: ListNode | null;
}

/**
 * **[23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/)**
 *
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * @param lists
 * @returns
 */
export default function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
	const listLength = lists.length;
	if (listLength === 0) return null;

	// 1. 找出头节点
	const head: ListNode | null = findNextNode(lists);
	if (head === null) return head;

	let current = head;

	let next: ListNode | null;
	while ((next = findNextNode(lists)) !== null) {
		current.next = next;
		current = next;
	}

	return head;
}

function findNextNode(lists: Array<ListNode | null>): ListNode | null {
	let next: ListNode | null = lists[0];
	let nextIdx: number = 0;
	const listLength = lists.length;
	for (let idx = 1; idx < listLength; idx++) {
		const a = lists[nextIdx],
			b = lists[idx];

		if (a === null) {
			next = b;
			nextIdx = idx;
			continue;
		}

		if (b !== null && a.val > b.val) {
			next = b;
			nextIdx = idx;
		}
	}

	if (!!next) {
		lists[nextIdx] = next.next;
	}

	return next;
}
